home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 60 / IOPROG_60.ISO / soft / c++ / gsl-1.1.1-setup.exe / {app} / src / eigen / symm.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-04-18  |  4.6 KB  |  180 lines
  1. /* eigen/symm.c
  2.  * 
  3.  * Copyright (C) 2001 Brian Gough
  4.  * 
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or (at
  8.  * your option) any later version.
  9.  * 
  10.  * This program is distributed in the hope that it will be useful, but
  11.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  * General Public License for more details.
  14.  * 
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. #include <config.h>
  21. #include <stdlib.h>
  22. #include <gsl/gsl_math.h>
  23. #include <gsl/gsl_vector.h>
  24. #include <gsl/gsl_matrix.h>
  25. #include <gsl/gsl_linalg.h>
  26. #include <gsl/gsl_eigen.h>
  27.  
  28. /* Compute eigenvalues/eigenvectors of real symmetric matrix using
  29.    reduction to tridiagonal form, followed by QR iteration with
  30.    implicit shifts.
  31.  
  32.    See Golub & Van Loan, "Matrix Computations" (3rd ed), Section 8.3
  33.    */
  34.  
  35. #include "qrstep.c"
  36.  
  37. gsl_eigen_symm_workspace *
  38. gsl_eigen_symm_alloc (const size_t n)
  39. {
  40.   gsl_eigen_symm_workspace *w;
  41.  
  42.   if (n == 0)
  43.     {
  44.       GSL_ERROR_NULL ("matrix dimension must be positive integer",
  45.               GSL_EINVAL);
  46.     }
  47.  
  48.   w = ((gsl_eigen_symm_workspace *)
  49.        malloc (sizeof (gsl_eigen_symm_workspace)));
  50.  
  51.   if (w == 0)
  52.     {
  53.       GSL_ERROR_NULL ("failed to allocate space for workspace", GSL_ENOMEM);
  54.     }
  55.  
  56.   w->d = (double *) malloc (n * sizeof (double));
  57.  
  58.   if (w->d == 0)
  59.     {
  60.       GSL_ERROR_NULL ("failed to allocate space for diagonal", GSL_ENOMEM);
  61.     }
  62.  
  63.   w->sd = (double *) malloc (n * sizeof (double));
  64.  
  65.   if (w->sd == 0)
  66.     {
  67.       GSL_ERROR_NULL ("failed to allocate space for subdiagonal", GSL_ENOMEM);
  68.     }
  69.  
  70.   w->size = n;
  71.  
  72.   return w;
  73. }
  74.  
  75. void
  76. gsl_eigen_symm_free (gsl_eigen_symm_workspace * w)
  77. {
  78.   free (w->sd);
  79.   free (w->d);
  80.   free (w);
  81. }
  82.  
  83.  
  84. int
  85. gsl_eigen_symm (gsl_matrix * A, gsl_vector * eval,
  86.              gsl_eigen_symm_workspace * w)
  87. {
  88.   if (A->size1 != A->size2)
  89.     {
  90.       GSL_ERROR ("matrix must be square to compute eigenvalues", GSL_ENOTSQR);
  91.     }
  92.   else if (eval->size != A->size1)
  93.     {
  94.       GSL_ERROR ("eigenvalue vector must match matrix size", GSL_EBADLEN);
  95.     }
  96.   else
  97.     {
  98.       const size_t N = A->size1;
  99.       double *const d = w->d;
  100.       double *const sd = w->sd;
  101.  
  102.       size_t a, b;
  103.  
  104.       /* handle special case */
  105.  
  106.       if (N == 1)
  107.     {
  108.       double A00 = gsl_matrix_get (A, 0, 0);
  109.       gsl_vector_set (eval, 0, A00);
  110.       return GSL_SUCCESS;
  111.     }
  112.  
  113.       /* use sd as the temporary workspace for the decomposition,
  114.          since we can discard the tau result immediately if we are not
  115.          computing eigenvectors */
  116.  
  117.       {
  118.     gsl_vector_view d_vec = gsl_vector_view_array (d, N);
  119.     gsl_vector_view sd_vec = gsl_vector_view_array (sd, N - 1);
  120.     gsl_vector_view tau = gsl_vector_view_array (sd, N - 1);
  121.     gsl_linalg_symmtd_decomp (A, &tau.vector);
  122.         gsl_linalg_symmtd_unpack_T (A, &d_vec.vector, &sd_vec.vector);
  123.       }
  124.       
  125.       /* Make an initial pass through the tridiagonal decomposition
  126.          to remove off-diagonal elements which are effectively zero */
  127.       
  128.       chop_small_elements (N, d, sd);
  129.       
  130.       /* Progressively reduce the matrix until it is diagonal */
  131.       
  132.       b = N - 1;
  133.       
  134.       while (b > 0)
  135.         {
  136.           if (sd[b - 1] == 0.0)
  137.             {
  138.               b--;
  139.               continue;
  140.             }
  141.           
  142.           /* Find the largest unreduced block (a,b) starting from b
  143.              and working backwards */
  144.           
  145.           a = b - 1;
  146.           
  147.           while (a > 0)
  148.             {
  149.               if (sd[a - 1] == 0.0)
  150.                 {
  151.                   break;
  152.                 }
  153.               a--;
  154.             }
  155.           
  156.           {
  157.             const size_t n_block = b - a + 1;
  158.             double *d_block = d + a;
  159.             double *sd_block = sd + a;
  160.             
  161.             /* apply QR reduction with implicit deflation to the
  162.                unreduced block */
  163.             
  164.             qrstep (n_block, d_block, sd_block, NULL, NULL);
  165.             
  166.             /* remove any small off-diagonal elements */
  167.             
  168.             chop_small_elements (n_block, d_block, sd_block);
  169.           }
  170.         }
  171.       
  172.       {
  173.         gsl_vector_view d_vec = gsl_vector_view_array (d, N);
  174.         gsl_vector_memcpy (eval, &d_vec.vector);
  175.       }
  176.  
  177.       return GSL_SUCCESS;
  178.     }
  179. }
  180.